#include <iostream>
#include <map>
using namespace std;

string minWindow(string S, string T) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(T.length() == 0)
        return "";
    if(S.length() == 0)
        return "";

    map<char, int> nearest;
    for(int i=0; i<T.length(); ++i){
        nearest[T[i]] = -1;
    }
    int findN = 0;

    int resLength = 0X7FFFFFFF;
    int resIndex = 0;

    for(int i=0; i<S.length(); ++i){
        map<char, int>::iterator it = nearest.find(S[i]);
        if(it != nearest.end()){
            if(it->second < 0){
                ++findN;
            }
            nearest[S[i]] = i;
            if(findN == T.length()){
                int farest = 0x7FFFFFFF;
                for(map<char, int>::iterator jt = nearest.begin(); 
                    jt != nearest.end(); 
                    ++jt){
                    if(jt->second < farest){
                        farest = jt->second;
                    }
                }
                int length = i - farest + 1;
                if(length < resLength){
                    resLength = length;
                    resIndex = farest;
                }
            }
        }
    }
    return S.substr(resIndex, resLength);
}

string minWindow1(string S, string T) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(T.length() == 0)
        return "";
    if(S.length() == 0 || T.length() > S.length())
        return "";

    map<char, int> target;
    map<char, int> cur;
    for(int i=0; i<T.length(); ++i){
        if(target.find(T[i]) == target.end()){
            target[T[i]] = 1;
            cur[T[i]] = 0;
        }
        else{
            target[T[i]] += 1;
        }
    }

    int head = 0;
    int tail = 0;
    int tarN = T.length();
    int curN = 0;
    int minLength = 0x7FFFFFFF;
    int minIndex = -1;
    for(head=0; head < S.length(); ++head){
        map<char, int>::iterator  it = cur.find(S[head]);
        if(it != cur.end()){
            if(cur[S[head]] < target[S[head]]){
                ++curN;
            }
            cur[S[head]] += 1;

            if(curN == tarN){
                while(tail <= head){
                    it = cur.find(S[tail]);
                    if(it != cur.end()){
                        if(cur[S[tail]] > target[S[tail]]){
                            cur[S[tail]] -= 1;
                        }
                        else{
                            break;
                        }
                    }
                    ++tail;
                }
                int length = head - tail + 1;
                if(length < minLength){
                    minLength = length;
                    minIndex = tail;
                }
            }
        }
    }
    if(minIndex < 0)
        return "";
    return S.substr(minIndex, minLength);
   
}

int main(){
    minWindow1("a","b");
    return 0;
}